#ifndef VIRTUAL_GRAPH_H_
#define VIRTUAL_GRAPH_H_

#include<unordered_set>
#include<queue>

#include "Algorithm.h"
#include "Graph.h"

class virtual_graph : public Algorithm{
    public:
        virtual_graph(){
            minDelay=kMaxValue;
        }
        ~virtual_graph();
        void SetupTopology(Graph* graph) override;
        Path FindPath(const Flow& flow) override{
            return pulse_findPath(flow.start,flow.end);
        };
        void updateVirGraph(Path p);
        void makeVirtualGraph();
        void Check();

    private:
        struct virtual_link{
            NodeId source_id; //虚拟边起点
            NodeId ter_id;    //虚拟边终点
            int cost;         //总损耗
            int delay_on;        //中继延迟
            std::vector<int> C_units;
            std::vector<int> nodes_passed;
            std::vector<Link *> links_passed;
            virtual_link(){}
            virtual_link(NodeId source):source_id(source),ter_id(source){
                cost = 0;
                delay_on = 0;
                C_units=Omega;
                nodes_passed.emplace_back(source);
            }
            virtual_link(virtual_link *lk){
                source_id=lk->source_id;
                ter_id=lk->ter_id;
                cost=lk->cost;
                delay_on=lk->delay_on;
                nodes_passed=lk->nodes_passed;
                links_passed=lk->links_passed;
                C_units=lk->C_units;
            }

            void Print(){
                for(int i=0;i<nodes_passed.size();i++){
                    std::cout<<nodes_passed[i]<<' ';
                }
                std::cout<<std::endl;
            }
        };

        std::vector<std::vector<virtual_link *>> virtual_adjList;
        int num_nodes_;
        //最终结果
        int minDelay;
        Path fianlPath;
        //多条flow时的最终结果
        std::vector<Path *> PathList;
        

    private:
        //寻路
        Path pulse_findPath(NodeId from, NodeId to);
        void Dfs(NodeId end,virtual_link *edge, Path p);

        //构建虚拟边
        void Dfs_virLink(virtual_link *lk,Link *link);

        //Helper Function
        bool judge(virtual_link *edge, Path p);
        std::vector<int> intersection(std::vector<int> v1,std::vector<int> v2);  //求可用资源交集

        //构建虚拟图的辅助函数
        bool isNodeEnd(NodeId n, virtual_link *vir_lk);
        bool isCopy(virtual_link *vir_lk) const;
};




#endif